package org.example;

import org.junit.jupiter.api.Test;

import java.util.*;
import java.util.stream.Collectors;

public class Sort implements ISwap {

    int partition(int[] nums,
                  int left,
                  int right) {
        int i = left, j = right, base = nums[left];
        while (i < j) {
            while (i < j && nums[j] >= base) {
                j--;
            }

            while (i < j && nums[i] <= base) {
                i++;
            }
            swap(nums, i, j);
        }

        swap(nums, left, i);
        return i;

    }

    void quickSort(int[] nums,
                   int left,
                   int right) {
        if (left >= right) {
            return;
        }

        int idx = partition(nums, left, right);
        quickSort(nums, left, idx - 1);
        quickSort(nums, idx + 1, right);
    }

    @Test
    void quickSort() {
        int[] nums = {2, 4, 1, 0, 3, 5};
        quickSort(nums, 0, nums.length - 1);
        for (int num : nums) {
            System.out.println(num);
        }
    }

    void merge(int[] nums,
               int left,
               int mid,
               int right) {
        int[] tmp = new int[right - left + 1];
        int i = left, j = mid + 1, k = 0;
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) {
                tmp[k++] = nums[i++];
            } else {
                tmp[k++] = nums[j++];
            }
        }

        while (i <= mid) {
            tmp[k++] = nums[i++];
        }
        while (j <= right) {
            tmp[k++] = nums[j++];
        }

        System.arraycopy(tmp, 0, nums, left, k);
    }

    @Test
    void mergeSort() {
        int[] nums = {7, 3, 2, 6, 0, 1, 5, 4};
        mergeSort(nums, 0, nums.length - 1);
        for (int num : nums) {
            System.out.println(num);
        }
    }

    void mergeSort(int[] nums,
                   int left,
                   int right) {
        if (left >= right) {
            return;
        }

        int mid = left + (right - left) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        merge(nums, left, mid, right);
    }

    void siftDown(int[] nums,
                  int n,
                  int i) {
        for (; ; ) {
            // 判断节点 i, l, r 中值最大的节点，记为 ma
            int left = 2 * i + 1;
            int right = 2 * i + 2;
            int ma = i;

            if (left < n && nums[left] > nums[ma]) {
                ma = left;
            }

            if (right < n && nums[right] > nums[ma]) {
                ma = right;
            }

            if (ma == i) {
                break;
            }

            swap(nums, ma, i);
            i = ma;
        }
    }

    @Test
    void heapSort() {
        int[] nums = {4, 1, 3, 1, 5, 2};
        for (int i = nums.length / 2 - 1; i >= 0; i--) {
            siftDown(nums, nums.length, i);
        }

        for (int i = nums.length - 1; i > 0; i--) {
            swap(nums, i, 0);
            siftDown(nums, i, 0);
        }

        System.out.println(22);
    }

    @Test
    void bucketSort() {
        double[] nums = {0.49, 0.96, 0.82, 0.09, 0.57, 0.43, 0.91, 0.75, 0.15, 0.37};
        int k = nums.length / 2;

        List<Double>[] lists = new List[k];

        for (double num : nums) {
            int idx = (int) (num * k);

            List<Double> list = lists[idx];
            if (list == null) {
                list = new ArrayList<>();
                lists[idx] = list;
            }

            list.add(num);
        }

        for (List<Double> list : lists) {
            Collections.sort(list);
        }

        Arrays.stream(lists).flatMap(list -> list.stream()).forEach(System.out::println);
    }

    @Test
    void bubbleSortWithFlag() {
        int[] nums = {4, 1, 3, 1, 5, 2};

        boolean flag = false;
        for (int i = nums.length - 1; i > 0; i--) {
            for (int j = 0; j < i; j++) {
                if (nums[j] > nums[j + 1]) {
                    swap(nums, j, j + 1);
                    flag = true;
                }
            }

            if (!flag) {
                break;
            }
        }

        Arrays.stream(nums).forEach(System.out::print);
    }
}
